<?php
/**
 * @title 733. 图像渲染 - 迭代+哈希
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param Integer[][] $image
     * @param Integer $sr
     * @param Integer $sc
     * @param Integer $newColor
     * @return Integer[][]
     */
    function floodFill($image, $sr, $sc, $newColor) {
        /**
         * @since 2020-08-17 哈希
         */
        $hashs = [];

        /**
         * @since 2020-08-17 宽,高
         */
        $width = count($image[0]);
        $height = count($image);
        
        /**
         * @since 2020-08-17 起始点颜色
         */
        $initColor = $image[$sr][$sc];
        $image[$sr][$sc] = $newColor;

        /**
         * @since 2020-08-17 迭代
         */
        $nexts = [[$sr,$sc]];
        while($nexts){
            $nextsTmp = [];

            /**
             * @since 2020-08-17 四个方向查找
             */
            foreach ($nexts as list($h, $w)){
                /**
                 * @since 2020-08-17 向上
                 */
                if($h>0 AND !isset($hashs[$h-1][$w]) AND $image[$h-1][$w] == $initColor){
                    $hashs[$h-1][$w] = 1;
                    $image[$h-1][$w] = $newColor;
                    $nextsTmp[] = [$h-1, $w];
                } else {}

                /**
                 * @since 2020-08-17 向下
                 */
                if($h<$height-1 AND !isset($hashs[$h+1][$w]) AND $image[$h+1][$w] == $initColor){
                    $hashs[$h+1][$w] = 1;
                    $image[$h+1][$w] = $newColor;
                    $nextsTmp[] = [$h+1, $w];
                } else {}

                /**
                 * @since 2020-08-17 向左
                 */
                if($w>0 AND !isset($hashs[$h][$w-1]) AND $image[$h][$w-1] == $initColor){
                    $hashs[$h][$w-1] = 1;
                    $image[$h][$w-1] = $newColor;
                    $nextsTmp[] = [$h, $w-1];
                } else {}

                /**
                 * @since 2020-08-17 向右
                 */
                if($w<$width-1 AND !isset($hashs[$h][$w+1]) AND $image[$h][$w+1] == $initColor){
                    $hashs[$h][$w+1] = 1;
                    $image[$h][$w+1] = $newColor;
                    $nextsTmp[] = [$h, $w+1];
                }
            }

            /**
             * @since 2020-08-17 下次迭代
             */
            $nexts = $nextsTmp;
        }

        /**
         * @return
         */
        return $image;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.16.php
 */
$datas = [
    [
        [[1,1,1],[1,1,0],[1,0,1]],1,1,2,
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->floodFill($data[0], $data[1], $data[2], $data[3]);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}
$xhprof->end();
